package 刷题.leedcode36;
//快慢指针法
public class PalindromeList3 {
    public boolean chkPalindrome(ListNode A){
        if(A == null || A.next ==null){
            return true;
        }
        ListNode prev =A;
        ListNode cur = A;
        //找中点
        while(prev != null && prev.next != null){
            prev = prev.next.next;
            cur = cur.next;
        }
        //翻转部分链表
        ListNode B = cur.next;
        while(B != null){
            ListNode next = B.next;
            B.next = cur;
            cur = B;
            B = next;
        }
        //对比
        while(A != cur){
            if(A.val != cur.val){
                return false;
            }
            if(A.next == cur){
                return true;
            }
            A = A.next;
            cur = cur.next;
        }
        return true;
    }
}
